package com.salim.leetcode.$86;

public class PartitionList {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode result = dummy;
        ListNode left = dummy;
        boolean change = false;
        while (dummy.next!=null){
            if(dummy.next.val>=x){
                dummy = dummy.next;
                change = true;
            }else{
                if(change){
                    ListNode next = dummy.next.next;
                    dummy.next.next = left.next;
                    left.next = dummy.next;
                    dummy.next = next;
                    left = left.next;
                }else{
                    left = left.next;
                    dummy = dummy.next;
                }
            }
        }
        return result.next;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
